/*
 * @Author: dadadaXU 1413107032@qq.com
 * @Date: 2025-02-20 12:28:46
 * @LastEditors: dadadaXU 1413107032@qq.com
 * @LastEditTime: 2025-02-20 13:37:36
 * @FilePath: \LeetCode\BinaryTree.hpp
 * @Description: LeetCode 二叉树构建
 */

#ifndef GENERATE_BINARYTREE_H
#define GENERATE_BINARYTREE_H

#define NULL_NODE std::numeric_limits<int>::min()

#include <vector>
#include <iostream>
#include <queue>

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

/**
 * [4,-7,-3,null,null,-9,-3 ,9,-7,-4,null,6,null,-6,-6,null,null,0,6,5,null,9,null,null,-1,-4,null,null,null,-2]
 *
 *                                         4,
 *                  -7,                                            -3,
 *          null,          null,                          -9,                     -3,
 *                                               9,              -7,         -4,         null,
 *                                           6,    null     -6,      -6,  null,null,
 *                                       0,     6,         5,null,  9,null,
 *                                   null,-1, -4,null, null,null, -2
 */

class BinaryTree
{
private:
public:
    TreeNode *rootNode_;

    BinaryTree() : rootNode_(nullptr) {}

    BinaryTree(const std::vector<int> &tree_nodes) : rootNode_(nullptr)
    {
        generateTree(tree_nodes);
    }

    ~BinaryTree()
    {
        deleteTree(rootNode_);
    }

    /// @brief 层序遍历生成二叉树
    /// @param tree_nodes 二叉树程序结果 空结点：NULL_NODE
    /// @return 二叉树根节点
    TreeNode *generateTree(const std::vector<int> &tree_nodes)
    {
        if (tree_nodes.empty())
            return nullptr;

        rootNode_ = new TreeNode(tree_nodes[0]);

        std::queue<TreeNode *> nodeQueue;
        nodeQueue.push(rootNode_);

        int i = 1; // tree_nodes 索引
        while (!nodeQueue.empty() && i < tree_nodes.size())
        {
            TreeNode *current = nodeQueue.front();
            nodeQueue.pop();

            if (tree_nodes[i] != NULL_NODE)
            {
                current->left = new TreeNode(tree_nodes[i]);
                nodeQueue.push(current->left);
            }
            i++;

            if (i < tree_nodes.size() && tree_nodes[i] != NULL_NODE)
            {
                current->right = new TreeNode(tree_nodes[i]);
                nodeQueue.push(current->right);
            }
            i++;
        }

        return rootNode_;
    }

    /// @brief 后续遍历删除二叉树
    /// @param root 根节点
    void deleteTree(TreeNode *root)
    {
        if (root == nullptr)
            return;

        deleteTree(root->left);
        deleteTree(root->right);

        delete root;
        root = nullptr;
    }

    /// @brief 二叉树最大深度
    /// @param root 根节点
    /// @return 最大深度
    int maxDepth(TreeNode *root)
    {
        if (root == nullptr)
            return 0;

        return std::max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }
};

#endif
